Date: Tue, 10 Dec 1996 21:21:42 GMT
Server: NCSA/1.4.2
Content-type: text/html
Last-modified: Mon, 04 Sep 1995 19:47:16 GMT
Content-length: 3084

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>Upper and Lower Bounds on Constructing Alphabetic Binary Trees</TITLE>
</HEAD>
<BODY>
<meta name="description" value="Upper and Lower Bounds on Constructing Alphabetic Binary Trees">
<meta name="keywords" value="mkbm">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><A NAME=tex2html3 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/homes/speed/figs/next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/homes/speed/figs/up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/homes/speed/figs/previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html4 HREF="node1.html"> Overview</A>
<BR> <HR> <P>
 <H1>Upper and Lower Bounds on Constructing Alphabetic Binary Trees</H1>
<P><STRONG>
MARIA KLAWE<A NAME=tex2html1 HREF="footnode.html#3"><IMG ALIGN=BOTTOM ALT="gif" SRC="http://www.cs.washington.edu/homes/speed/figs/foot_motif.gif"></A> and
BRENDAN MUMEY<A NAME=tex2html2 HREF="footnode.html#4"><IMG ALIGN=BOTTOM ALT="gif" SRC="http://www.cs.washington.edu/homes/speed/figs/foot_motif.gif"></A>
</STRONG><P>
<P><STRONG></STRONG><P>
<P>
<H3>Abstract:</H3>
<EM>This paper studies the long-standing open question of whether
optimal alphabetic binary trees can be constructed in <IMG  ALIGN=MIDDLE ALT="" SRC="img3.gif"> 
time.  We show that a class of techniques for 
finding optimal alphabetic trees which includes all current 
methods yielding <IMG  ALIGN=MIDDLE ALT="" SRC="img4.gif"> time algorithms are at least
as hard as sorting in whatever model of computation is used.
We also give <IMG  ALIGN=MIDDLE ALT="" SRC="img5.gif"> time algorithms for the case where all the input
weights are within a constant factor of one another and when
they are exponentially separated.
</EM><P>
<BR> <HR>
<UL> 
<LI> <A NAME=tex2html5 HREF="node1.html#SECTION00010000000000000000"> Overview</A>
<LI> <A NAME=tex2html6 HREF="node2.html#SECTION00020000000000000000"> Current Methods</A>
<LI> <A NAME=tex2html7 HREF="node3.html#SECTION00030000000000000000"> Region-based Methods</A>
<LI> <A NAME=tex2html8 HREF="node4.html#SECTION00040000000000000000"> The Constant Factor Case</A>
<LI> <A NAME=tex2html9 HREF="node5.html#SECTION00050000000000000000"> Hardness Results</A>
<UL> 
<LI> <A NAME=tex2html10 HREF="node6.html#SECTION00051000000000000000"> Finding the lmcp tree</A>
<LI> <A NAME=tex2html11 HREF="node7.html#SECTION00052000000000000000"> Region-based Methods</A>
</UL> 
<LI> <A NAME=tex2html12 HREF="node8.html#SECTION00060000000000000000"> Conclusions</A>
<LI> <A NAME=tex2html13 HREF="node9.html#SECTION00070000000000000000">References</A>
<LI> <A NAME=tex2html14 HREF="node10.html#SECTION00080000000000000000">   About this document ... </A>
</UL>
<BR> <HR>
<P><ADDRESS>
<I>Brendan Mumey <BR>
Mon Sep  4 11:52:47 PDT 1995</I>
</ADDRESS>
</BODY>
